Travelling Salesman Problem

What is TSP?

The Travelling Salesman Problem (TSP) is one of the most famous problems in computer science. It asks: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"

The Algorithm

This visualization uses a genetic algorithm to find an optimal solution. The algorithm works by:

• Creating an initial population of random routes
• Evaluating each route's fitness (total distance)
• Selecting the best routes to create new solutions
• Applying mutations to maintain diversity

How to Use

• Click on the map to add cities (points)
• Use 'Random Points' to generate random cities
• Click 'Solve' to find the optimal route
• Use 'Step' to see the solution build step by step

Fun Facts

• TSP is an NP-hard problem in combinatorial optimization
• It has applications in logistics, microchip manufacturing, and DNA sequencing
• The number of possible routes grows factorially with the number of cities